package leetcode.others;

// 390. 消除游戏
public class LastRemaining {
    public static void main(String[] args) {

    }


    public static int lastRemaining(int n) {
        //头指针
        int head = 1;
        //方向标
        boolean left = true;
        //步长，本题解并不是真的删除数据，而是通过改变步长大小来做到删除数据的效果
        int step = 1;
        //当只有一个数字的时候结束循环
        while (n > 1) {
            //从左边开始，或者从右边开始，但数列的总数为奇数时
            if (left || (n % 2 != 0)) {
                head += step;
            }
            //步长增加，表示删除
            step *= 2;
            //取反，表示转向
            left = !left;
            n /= 2;
        }
        return head;
    }
}
